package com.zdp.leetcodeMiddle;

/*
* 题目描述：
* 在组合数学中，如果一个排列中所有元素都不在原先的位置上，那么这个排列就被称为错位排列。
给定一个从 1 到 n 升序排列的数组，你可以计算出总共有多少个不同的错位排列吗？
由于答案可能非常大，你只需要将答案对 109+7 取余输出即可。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-derangement-of-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 寻找数组的错位排列 {
    /*
    * 解题思路：
    * 一个长度为n的数组，如果我们先对一个数进行换位（假设该数为x），那么这个数可以有n-1种换位选择
    * 假设x与y进了换位，那么接下来就有两种情况
    * 1. 因为x和y进行了换位，所以x和y目前都是错位，那么可以不对y进行处理，那么只需要对剩下的n-2个数进行错位排列即可
    * 2. 对y也进行换位处理，因为x和y进行了换位，那么y不能和当前x所在位置换位，所以要对剩下的n-1个数进行错位排列，排除掉x
    * 那么可以得到式子 f(n) = (n-1)*(f(n-1)+f(n-2))
    * */
    public int findDerangement(int n) {
        if(n<=2){
            return n==1?0:1;
        }
        int[] dp = new int[n+1];
        dp[1] = 0;
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            dp[i] = (int)((i-1L)*(dp[i-1]+dp[i-2]))%1000000007;
        }
        return dp[n];
    }
    //可以空间优化一下，用两个变量代替数组
    public int findDerangement1(int n) {
        if(n<=2){
            return n==1?0:1;
        }
        int a1 = 0;
        int a2 = 1;
        int result = 0;
        for(int i=3;i<=n;i++){
            result = (int)((i-1L)*(a1+a2)%1000000007);
            a1 = a2;
            a2 = result;
        }
        return result;
    }
}
